{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Non-Overlapping Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNumOfSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最多的不重叠子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个只包含小写字母的字符串&nbsp;<code>s</code>&nbsp;，你需要找到 <code>s</code>&nbsp;中最多数目的非空子字符串，满足如下条件：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>这些字符串之间互不重叠，也就是说对于任意两个子字符串&nbsp;<code>s[i..j]</code> 和&nbsp;<code>s[x..y]</code>&nbsp;，要么&nbsp;<code>j &lt; x</code>&nbsp;要么&nbsp;<code>i &gt; y</code>&nbsp;。</li>\n",
    "\t<li>如果一个子字符串包含字符&nbsp;<code>char</code> ，那么&nbsp;<code>s</code>&nbsp;中所有&nbsp;<code>char</code> 字符都应该在这个子字符串中。</li>\n",
    "</ol>\n",
    "\n",
    "<p>请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。</p>\n",
    "\n",
    "<p>请注意，你可以以 <strong>任意</strong>&nbsp;顺序返回最优解的子字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"adefaddaccc\"\n",
    "<strong>输出：</strong>[\"e\",\"f\",\"ccc\"]\n",
    "<strong>解释：</strong>下面为所有满足第二个条件的子字符串：\n",
    "[\n",
    "&nbsp; \"adefaddaccc\"\n",
    "&nbsp; \"adefadda\",\n",
    "&nbsp; \"ef\",\n",
    "&nbsp; \"e\",\n",
    "  \"f\",\n",
    "&nbsp; \"ccc\",\n",
    "]\n",
    "如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1 。如果我们选择 \"adefadda\" ，剩下子字符串中我们只可以选择 \"ccc\" ，它是唯一不重叠的子字符串，所以答案为 2 。同时我们可以发现，选择 \"ef\" 不是最优的，因为它可以被拆分成 2 个子字符串。所以最优解是选择 [\"e\",\"f\",\"ccc\"] ，答案为 3 。不存在别的相同数目子字符串解。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abbaccd\"\n",
    "<strong>输出：</strong>[\"d\",\"bb\",\"cc\"]\n",
    "<strong>解释：</strong>注意到解 [\"d\",\"abba\",\"cc\"] 答案也为 3 ，但它不是最优解，因为它的总长度更长。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-non-overlapping-substrings](https://leetcode.cn/problems/maximum-number-of-non-overlapping-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-non-overlapping-substrings](https://leetcode.cn/problems/maximum-number-of-non-overlapping-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"adefaddaccc\"', '\"abbaccd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        segs = [[-1,-1] for _ in range(26)]\n",
    "        for i, c in enumerate(s):\n",
    "            j = ord(c) - ord('a')\n",
    "            if segs[j][0] == -1:\n",
    "                segs[j][0] = segs[j][1] = i\n",
    "            else: segs[j][1] = max(segs[j][1], i)\n",
    "        \n",
    "        for i in range(26):\n",
    "            if segs[i][0] == -1: continue\n",
    "            j = segs[i][0]\n",
    "            while j <= segs[i][1]:\n",
    "                k = ord(s[j]) - ord('a')\n",
    "                if segs[i][0] <= segs[k][0] and segs[i][1] >= segs[k][1]:\n",
    "                    j += 1\n",
    "                    continue \n",
    "                segs[i][0] = min(segs[k][0], segs[i][0])\n",
    "                segs[i][1] = max(segs[k][1], segs[i][1])    \n",
    "                j = segs[i][0] + 1 \n",
    "        segs.sort(key = lambda x: x[1])\n",
    "        ans  = []\n",
    "        last = -1\n",
    "        for seg in segs:\n",
    "            if seg[0] != -1 and seg[0] > last:\n",
    "                ans.append(s[seg[0]:seg[1] + 1])\n",
    "                last = seg[1]\n",
    "        return ans\n",
    "'''\n",
    "    最多的子串，且总长度最小\n",
    "    统计每个字符的区间，扩展这个区间到条件2，包换全部的字符\n",
    "    按照区间右端点和区间长度从小到大排序\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        seg = [[-1,-1] for _ in range(26)]\n",
    "        for i in range(len(s)):\n",
    "            charIdx = ord(s[i])-ord('a')\n",
    "            if seg[charIdx][0] == -1:\n",
    "                seg[charIdx][0], seg[charIdx][1] = i,i\n",
    "            else:\n",
    "                seg[charIdx][1] = i\n",
    "        \n",
    "        for i in range(26):\n",
    "            if seg[i][0]!=-1:\n",
    "                j = seg[i][0]\n",
    "                while j<=seg[i][1]:\n",
    "                    charIdx = ord(s[j])-ord('a')\n",
    "                    if seg[i][0]<=seg[charIdx][0] and seg[charIdx][1]<=seg[i][1]:\n",
    "                        pass\n",
    "                    else:\n",
    "                        seg[i][0] = min(seg[i][0], seg[charIdx][0])\n",
    "                        seg[i][1] = max(seg[i][1], seg[charIdx][1])\n",
    "                        j = seg[i][0]\n",
    "                    j+=1\n",
    "            \n",
    "        seg.sort(key=lambda x:(x[1], -x[0]))\n",
    "        ans = []\n",
    "        end = -1\n",
    "        for segment in seg:\n",
    "            left,right = segment[0], segment[1]\n",
    "            if left == -1:\n",
    "                continue\n",
    "            if end==-1 or left>end:\n",
    "                end = right\n",
    "                ans.append(s[left:right+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        segs = [[-1,-1] for _ in range(26)]\n",
    "        for i, c in enumerate(s):\n",
    "            j = ord(c) - ord('a')\n",
    "            if segs[j][0] == -1:\n",
    "                segs[j][0] = segs[j][1] = i\n",
    "            else: segs[j][1] = max(segs[j][1], i)\n",
    "        \n",
    "        for i in range(26):\n",
    "            if segs[i][0] == -1: continue\n",
    "            j = segs[i][0]\n",
    "            while j <= segs[i][1]:\n",
    "                k = ord(s[j]) - ord('a')\n",
    "                if segs[i][0] <= segs[k][0] and segs[i][1] >= segs[k][1]:\n",
    "                    j += 1\n",
    "                    continue \n",
    "                segs[i][0] = min(segs[k][0], segs[i][0])\n",
    "                segs[i][1] = max(segs[k][1], segs[i][1])    \n",
    "                j = segs[i][0] + 1 \n",
    "        segs = sorted(segs, key = lambda x: x[1])\n",
    "        ans  = []\n",
    "        last = -1\n",
    "        for seg in segs:\n",
    "            if seg[0] != -1 and seg[0] > last:\n",
    "                ans.append(s[seg[0]:seg[1] + 1])\n",
    "                last = seg[1]\n",
    "        return ans\n",
    "'''\n",
    "    最多的子串，且总长度最小\n",
    "    统计每个字符的区间，扩展这个区间到条件2，包换全部的字符\n",
    "    按照区间右端点和区间长度从小到大排序\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "        visited = set()\n",
    "\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "        \n",
    "        marks = []\n",
    "        for char in left:\n",
    "            if char in visited:\n",
    "                continue\n",
    "            l, r = left[char], right[char]\n",
    "            find = True\n",
    "            while l <= r:\n",
    "                if left[s[l]] < left[char]:\n",
    "                    find = False\n",
    "                    break\n",
    "                if right[s[l]] >= r:\n",
    "                    r = right[s[l]]\n",
    "                l += 1\n",
    "            if find:\n",
    "                marks.append([left[char], r])\n",
    "\n",
    "\n",
    "        # for char in left:\n",
    "        #     l, r = left[char], right[char]\n",
    "        #     for j in range(l, r + 1):\n",
    "        #         right[char] = max(right[char], right[s[j]])\n",
    "        #         left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        # for char in left:\n",
    "        #     l, r = left[char], right[char]\n",
    "        #     for j in range(l, r + 1):\n",
    "        #         right[char] = max(right[char], right[s[j]])\n",
    "        #         left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        # marks = [[left[char], right[char]] for char in left]\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        # print(marks)\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        # 首先算出包含每种字母的最小区间（最左端点和最右端点）\n",
    "        # 然后需要扩展每种字母的区间（根据区间内其他字母的范围），因为要满足条件2\n",
    "        # 最后问题变成，用已有的区间，去覆盖整个线段，且区间不重叠，数量最多，总长度最小\n",
    "        # 则根据右端点为第一关键字，长度为第二关键字排序，按顺序取区间，保证不重叠即可\n",
    "        seg = [[-1,-1] for _ in range(26)]\n",
    "        for i in range(len(s)):\n",
    "            charIdx = ord(s[i])-ord('a')\n",
    "            if seg[charIdx][0] == -1:\n",
    "                seg[charIdx][0], seg[charIdx][1] = i,i\n",
    "            else:\n",
    "                seg[charIdx][1] = i\n",
    "        \n",
    "        for i in range(26):\n",
    "            if seg[i][0]!=-1:\n",
    "                j = seg[i][0]\n",
    "                while j<=seg[i][1]:\n",
    "                    charIdx = ord(s[j])-ord('a')\n",
    "                    if seg[i][0]<=seg[charIdx][0] and seg[charIdx][1]<=seg[i][1]:\n",
    "                        pass\n",
    "                    else:\n",
    "                        seg[i][0] = min(seg[i][0], seg[charIdx][0])\n",
    "                        seg[i][1] = max(seg[i][1], seg[charIdx][1])\n",
    "                        j = seg[i][0]\n",
    "                    j+=1\n",
    "            \n",
    "        seg.sort(key=lambda x:(x[1], -x[0]))\n",
    "        ans = []\n",
    "        end = -1\n",
    "        for segment in seg:\n",
    "            left,right = segment[0], segment[1]\n",
    "            if left == -1:\n",
    "                continue\n",
    "            if end==-1 or left>end:\n",
    "                end = right\n",
    "                ans.append(s[left:right+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Seg:\n",
    "    def __init__(self, left=-1, right=-1):\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    \n",
    "    def __lt__(self, rhs):\n",
    "        return self.left > rhs.left if self.right == rhs.right else self.right < rhs.right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        seg = [Seg() for _ in range(26)]\n",
    "        # 预处理左右端点\n",
    "        for i in range(len(s)):\n",
    "            charIdx = ord(s[i]) - ord('a')\n",
    "            if seg[charIdx].left == -1:\n",
    "                seg[charIdx].left = seg[charIdx].right = i\n",
    "            else:\n",
    "                seg[charIdx].right = i\n",
    "\n",
    "        for i in range(26):\n",
    "            if seg[i].left != -1:\n",
    "                j = seg[i].left\n",
    "                while j <= seg[i].right:\n",
    "                    charIdx = ord(s[j]) - ord('a')\n",
    "                    if seg[i].left <= seg[charIdx].left and seg[charIdx].right <= seg[i].right:\n",
    "                        pass\n",
    "                    else:\n",
    "                        seg[i].left = min(seg[i].left, seg[charIdx].left)\n",
    "                        seg[i].right = max(seg[i].right, seg[charIdx].right)\n",
    "                        j = seg[i].left\n",
    "                    j += 1\n",
    "\n",
    "        # 贪心选取\n",
    "        seg.sort()\n",
    "        ans = list()\n",
    "        end = -1\n",
    "        for segment in seg:\n",
    "            left, right = segment.left, segment.right\n",
    "            if left == -1:\n",
    "                continue\n",
    "            if end == -1 or left > end:\n",
    "                end = right\n",
    "                ans.append(s[left:right+1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        left = {}\n",
    "        right = {}\n",
    "        for i in range(n):\n",
    "            if s[i] not in left:\n",
    "                left[s[i]] = i \n",
    "            right[s[i]] = i \n",
    "        ends = sorted(right.values())\n",
    "        res = []\n",
    "        pre = 0\n",
    "        for e in ends:\n",
    "            start = left[s[e]]\n",
    "            cur = e\n",
    "            while cur >= start:\n",
    "                l, r = left[s[cur]], right[s[cur]]\n",
    "                if l < pre or r > e:\n",
    "                    break \n",
    "                cur -= 1 \n",
    "                start = min(start, l)\n",
    "            else:\n",
    "                res.append(s[start : e + 1])\n",
    "                pre = e \n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "        \n",
    "        marks = []\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            find = True\n",
    "            while l <= r:\n",
    "                if left[s[l]] < left[char]:\n",
    "                    find = False\n",
    "                    break\n",
    "                if right[s[l]] > r:\n",
    "                    r = right[s[l]]\n",
    "                l += 1\n",
    "            if find:\n",
    "                marks.append([left[char], r])\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        # print(marks)\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "    最多的子串，且总长度最小\n",
    "    统计每个字符的区间，扩展这个区间到条件2，包换全部的字符\n",
    "    按照区间右端点和区间长度从小到大排序\n",
    "'''\n",
    "def idx(c): return ord(c) - ord('a')\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        def expnad_1(segs):\n",
    "            for i in range(26):\n",
    "                if segs[i][0] == -1: continue\n",
    "                j = segs[i][0]\n",
    "                while j <= segs[i][1]:\n",
    "                    k = idx(s[j])\n",
    "                    if segs[i][0] <= segs[k][0] and segs[i][1] >= segs[k][1]:\n",
    "                        j += 1\n",
    "                        continue \n",
    "                    segs[i][0] = min(segs[k][0], segs[i][0])\n",
    "                    segs[i][1] = max(segs[k][1], segs[i][1])    \n",
    "                    j = segs[i][0] + 1 \n",
    "                    \n",
    "        def expnad_2(segs):\n",
    "            for i in range(26):\n",
    "                if segs[i][0] == -1: continue\n",
    "                l, r = segs[i][0], segs[i][0]\n",
    "                while l >= segs[i][0] or r <= segs[i][1]:\n",
    "                    # 左边界扩展\n",
    "                    while l >= segs[i][0]:\n",
    "                        k = idx(s[l])\n",
    "                        segs[i][0] = min(segs[i][0], segs[k][0])\n",
    "                        segs[i][1] = max(segs[k][1], segs[i][1])    \n",
    "                        l -= 1\n",
    "\n",
    "                    # 右边界扩展\n",
    "                    while r <= segs[i][1]:\n",
    "                        k = idx(s[r])\n",
    "                        segs[i][0] = min(segs[i][0], segs[k][0])\n",
    "                        segs[i][1] = max(segs[k][1], segs[i][1])    \n",
    "                        r += 1\n",
    "\n",
    "        segs = [[-1,-1] for _ in range(26)]\n",
    "        for i, c in enumerate(s):\n",
    "            j = idx(c)\n",
    "            if segs[j][0] == -1:\n",
    "                segs[j][0] = segs[j][1] = i\n",
    "            else: segs[j][1] = max(segs[j][1], i)\n",
    "        expnad_2(segs)\n",
    "        segs.sort(key = lambda x: x[1])\n",
    "        ans  = []\n",
    "        last = -1\n",
    "        for seg in segs:\n",
    "            if seg[0] != -1 and seg[0] > last:\n",
    "                ans.append(s[seg[0]:seg[1] + 1])\n",
    "                last = seg[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        seen = dict()\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] not in seen:\n",
    "                seen[s[i]] = [i, i]\n",
    "            seen[s[i]][1] = i\n",
    "        for char in seen:\n",
    "            j = seen[char][0]\n",
    "            while j <= seen[char][1]:\n",
    "                if seen[char][0] <= seen[s[j]][0] and seen[char][1] >= seen[s[j]][1]:\n",
    "                    pass\n",
    "                else:\n",
    "                    seen[char][0] = min(seen[char][0], seen[s[j]][0])\n",
    "                    seen[char][1] = max(seen[char][1], seen[s[j]][1])\n",
    "                j += 1\n",
    "        arr = list(seen.values())\n",
    "        arr.sort(key=lambda x: x[1]*(n+1)+(x[1]-x[0]))\n",
    "        stk = []\n",
    "        for d in arr:\n",
    "            if len(stk) == 0 or stk[-1][1] < d[0]:\n",
    "                stk.append(d)\n",
    "        return [s[d[0]:d[1]+1] for d in stk]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        left = {}\n",
    "        right = {}\n",
    "        for i in range(n):\n",
    "            if s[i] not in left:\n",
    "                left[s[i]] = i \n",
    "            right[s[i]] = i \n",
    "        ends = sorted(right.values())\n",
    "        pre = 0\n",
    "        res = []\n",
    "        for e in ends:\n",
    "            start = left[s[e]] \n",
    "            cur = e \n",
    "            while cur >= start:\n",
    "                l, r = left[s[cur]], right[s[cur]]\n",
    "                if l < pre or r > e:\n",
    "                    break \n",
    "                start = min(start, l)\n",
    "                cur -= 1 \n",
    "            else:\n",
    "                res.append(s[start : e + 1])\n",
    "                pre = e \n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l, r):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "\n",
    "    def __lt__(self, other):  # 重写 less_than 小于号 '<'\n",
    "        if self.r == other.r:\n",
    "            return self.l > other.l  # r相同，为了让长度更短，要l大的\n",
    "        else:\n",
    "            return self.r < other.r  # 贪心，为了尽可能多的子串\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        head = dict()  # 字母第一次出现的位置\n",
    "        tail = dict()  # 字母最后一次出现的位置\n",
    "        for i in range(n):\n",
    "            if s[i] not in head:\n",
    "                head[s[i]] = i\n",
    "            tail[s[i]] = i\n",
    "\n",
    "        def get_end_start_from_i(i):  # 以i为起始端的，合理str的末位index（含）\n",
    "            end = tail[s[i]]\n",
    "            j = i + 1\n",
    "            while j < end:  # end是在动态向右扩展的\n",
    "                if head[s[j]] < i:\n",
    "                    return -1\n",
    "                end = max(end, tail[s[j]])\n",
    "                j += 1\n",
    "            return end\n",
    "\n",
    "        nodes = []\n",
    "        for i in range(26):\n",
    "            c = chr(ord(\"a\") + i)\n",
    "            if c in head:\n",
    "                l = head[c]\n",
    "                r = get_end_start_from_i(l)\n",
    "                if r != -1:\n",
    "                    nodes.append(Node(l, r))\n",
    "\n",
    "        nodes.sort()  # 按照每条线段的R端从小到大排序  如果R端相同，则L从大到小（R-L为长度，长度更短（题目要求的））\n",
    "\n",
    "        res = []\n",
    "        pre = -1\n",
    "        for node in nodes:\n",
    "            l, r = node.l, node.r\n",
    "            if l > pre:\n",
    "                res.append(s[l : r + 1])\n",
    "                pre = r\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "        \n",
    "        marks = []\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            find = True\n",
    "            while l <= r:\n",
    "                if left[s[l]] < left[char]:\n",
    "                    find = False\n",
    "                    break\n",
    "                if right[s[l]] > r:\n",
    "                    r = right[s[l]]\n",
    "                l += 1\n",
    "            if find:\n",
    "                marks.append([left[char], r])\n",
    "\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, l, r):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "\n",
    "    def __lt__(self, other):  # 重写 less_than 小于号 '<'\n",
    "        if self.r == other.r:\n",
    "            return self.l > other.l  # r相同，为了让长度更短，要l大的\n",
    "        else:\n",
    "            return self.r < other.r  # 贪心，为了尽可能多的子串\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        head = dict()  # 字母第一次出现的位置\n",
    "        tail = dict()  # 字母最后一次出现的位置\n",
    "        for i in range(n):\n",
    "            if s[i] not in head:\n",
    "                head[s[i]] = i\n",
    "            tail[s[i]] = i\n",
    "\n",
    "        def get_end_start_from_i(i):  # 以L为起始端的，合理str的末位index（含）\n",
    "            end = tail[s[i]]\n",
    "            j = i + 1\n",
    "            while j < end:  # end是在动态向右扩展的\n",
    "                if head[s[j]] < i:\n",
    "                    return -1\n",
    "                end = max(end, tail[s[j]])\n",
    "                j += 1\n",
    "            return end\n",
    "\n",
    "        nodes = []\n",
    "        for ID in range(26):\n",
    "            c = chr(ord(\"a\") + ID)\n",
    "            if c in head:\n",
    "                l = head[c]\n",
    "                r = get_end_start_from_i(l)\n",
    "                if r != -1:\n",
    "                    nodes.append(Node(l, r))\n",
    "\n",
    "        nodes.sort()  # 按照每条线段的R端从小到大排序  如果R端相同，则L从大到小（R-L为长度，长度更短（题目要求的））\n",
    "\n",
    "        res = []\n",
    "        curR = -1\n",
    "        for node in nodes:\n",
    "            l, r = node.l, node.r\n",
    "            if l > curR:\n",
    "                res.append(s[l : r + 1])\n",
    "                curR = r\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        pos = defaultdict(list)\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            if len(pos[ch]) == 2:\n",
    "                pos[ch].pop()\n",
    "            pos[ch].append(i)\n",
    "\n",
    "        q = []\n",
    "        for ch, v in pos.items():\n",
    "            L, R = v[0], v[-1]\n",
    "            if L == R:\n",
    "                q.append((L, R))\n",
    "                continue\n",
    "\n",
    "            i = L + 1\n",
    "            while i < R:\n",
    "                ch = s[i]\n",
    "                if pos[ch][0] < L:\n",
    "                    L = -1\n",
    "                    break\n",
    "                R = max(R, pos[ch][-1])\n",
    "                i += 1\n",
    "            if L != -1:\n",
    "                q.append((L, R))\n",
    "\n",
    "        q.sort(key=lambda e: (e[1], e[1] - e[0]))\n",
    "\n",
    "        p = -1\n",
    "        res = []\n",
    "        for x, y in q:\n",
    "            if x > p:\n",
    "                res.append(s[x : y + 1])\n",
    "            p = y\n",
    "        # print(q)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "        \n",
    "        # def expand(char, visited):\n",
    "        #     if char in visited:\n",
    "        #         return\n",
    "        #     l, r = left[char], right[char]\n",
    "        #     for j in range(l, r + 1):\n",
    "        #         if s[j] not in visited:\n",
    "        #             expand(s[j], visited)\n",
    "        #         right[char] = max(right[char], right[s[j]])\n",
    "        #         left[char] = min(left[char], left[s[j]])\n",
    "        #     visited.add(char)\n",
    "        #     return\n",
    "        \n",
    "        # visited = set()\n",
    "        # for char in left:\n",
    "        #     expand(char, visited)\n",
    "        \n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        marks = [[left[char], right[char]] for char in left]\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        # print(marks)\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        marks = [[left[char], right[char]] for char in left]\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        # print(marks)\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        D = {}\n",
    "        revD = {}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] not in D:D[s[i]] = i+1\n",
    "        for i in range(n):\n",
    "            if s[i] not in revD:revD[s[i]] = i\n",
    "        L = [[0,n]]\n",
    "        temp = []\n",
    "        Res = []\n",
    "        while temp != L:\n",
    "            temp = L\n",
    "            L = []\n",
    "            for (strt,end) in temp:\n",
    "                pos = strt\n",
    "                flag = False\n",
    "                while pos < end:\n",
    "                    if revD[s[pos]] < pos:pos+=1;continue\n",
    "                    mx = D[s[pos]];mn = revD[s[pos]];ff = 1\n",
    "                    i = pos+1\n",
    "                    while i < mx:\n",
    "                        mx = max(mx,D[s[i]]);mn = min(mn,revD[s[i]])\n",
    "                        if (not flag and mx == end) or mn < pos:pos += 1;ff = 0;break\n",
    "                        i += 1\n",
    "                    if ff:\n",
    "                        flag = True\n",
    "                        L.append([pos,mx])\n",
    "                        pos = mx\n",
    "                if not flag:Res.append([strt,end])\n",
    "        L.extend(Res)\n",
    "        return [s[a:b] for (a,b) in L]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "        \n",
    "        \n",
    "        # for i, char in enumerate(s):\n",
    "        #     l, r = left[char], right[char]\n",
    "        #     for j in range(l, r + 1):\n",
    "        #         right[char] = max(right[char], right[s[j]])\n",
    "        #         left[char] = min(left[char], left[s[j]])\n",
    "        \n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        marks = [[left[char], right[char]] for char in left]\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        # print(marks)\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        D = {}\n",
    "        revD = {}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] not in D:D[s[i]] = i+1\n",
    "        for i in range(n):\n",
    "            if s[i] not in revD:revD[s[i]] = i\n",
    "        L = [[0,n]]\n",
    "        temp = []\n",
    "        Res = []\n",
    "        while temp != L:\n",
    "            temp = L\n",
    "            L = []\n",
    "            for (strt,end) in temp:\n",
    "                pos = strt\n",
    "                flag = False\n",
    "                while pos < end:\n",
    "                    if revD[s[pos]] < pos:pos+=1;continue\n",
    "                    mx = D[s[pos]];mn = revD[s[pos]];ff = 1\n",
    "                    i = pos+1\n",
    "                    while i < mx:\n",
    "                        mx = max(mx,D[s[i]]);mn = min(mn,revD[s[i]])\n",
    "                        if (not flag and mx == end) or mn < pos:pos += 1;ff = 0;break\n",
    "                        i += 1\n",
    "                    if ff:\n",
    "                        flag = True\n",
    "                        L.append([pos,mx])\n",
    "                        pos = mx\n",
    "                if not flag:Res.append([strt,end])\n",
    "        Res.extend(L)\n",
    "        return [s[a:b] for (a,b) in Res]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "        \n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "\n",
    "        marks = [[left[char], right[char]] for char in left]\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        # print(marks)\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        left = {char: len(s) for char in s}\n",
    "        right = {char: -1 for char in s}\n",
    "        for i, char in enumerate(s):\n",
    "            left[char] = min(i, left[char])\n",
    "            right[char] = max(i, right[char])\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "        for char in left:\n",
    "            l, r = left[char], right[char]\n",
    "            for j in range(l, r + 1):\n",
    "                right[char] = max(right[char], right[s[j]])\n",
    "                left[char] = min(left[char], left[s[j]])\n",
    "        marks = [[left[char], right[char]] for char in left]\n",
    "        marks.sort(key = lambda x: x[1])\n",
    "        # print(marks)\n",
    "        ans = []\n",
    "        for mark in marks:\n",
    "            if ans and ans[-1][1] > mark[0]:\n",
    "                continue\n",
    "            ans.append(mark)\n",
    "        return [s[mark[0] : mark[1] + 1] for mark in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        dic = defaultdict(list)\n",
    "        right = -1\n",
    "        for i, x in enumerate(s):\n",
    "            dic[x].append(i)\n",
    "        for i, x in enumerate(s):\n",
    "            if dic[x][-1] == i:\n",
    "                j, left = i, dic[x][0]\n",
    "                if left < right:\n",
    "                    continue\n",
    "                while j > left:\n",
    "                    y = s[j]\n",
    "                    if dic[y][0] < right or dic[y][-1] > i:\n",
    "                        break\n",
    "                    left = min(left, dic[y][0])\n",
    "                    j -= 1\n",
    "                if j == left:\n",
    "                    right = i\n",
    "                    ans.append(s[left:right+1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        dic = defaultdict(list)\n",
    "        right = -1\n",
    "        for i, x in enumerate(s):\n",
    "            dic[x].append(i)\n",
    "        for i, x in enumerate(s):\n",
    "            if dic[x][-1] == i:\n",
    "                j, left = i, dic[x][0]\n",
    "                if left < right:\n",
    "                    continue\n",
    "                while j > left:\n",
    "                    y = s[j]\n",
    "                    if dic[y][0] < right or dic[y][-1] > i:\n",
    "                        break\n",
    "                    left = min(left, dic[y][0])\n",
    "                    j -= 1\n",
    "                if j == left:\n",
    "                    right = i\n",
    "                    ans.append(s[left:right+1])\n",
    "\n",
    "        return ans if ans else [s]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        d = defaultdict(list)\n",
    "        chs = set(s)\n",
    "        n = len(s)\n",
    "        for i, j in enumerate(s):\n",
    "            d[j].append(i)\n",
    "        L = []\n",
    "        for ch in chs:\n",
    "            start = d[ch][0]\n",
    "            i = start\n",
    "            end = d[ch][-1]\n",
    "            while i < n:\n",
    "                if i == end:\n",
    "                    L.append([start, end])\n",
    "                    break\n",
    "                if d[s[i]][0] < start:\n",
    "                    break\n",
    "                end = max(end, d[s[i]][-1])\n",
    "                i += 1\n",
    "        while 1:\n",
    "            n = len(L)\n",
    "            to_del = []\n",
    "            flag = False\n",
    "            for i in range(n - 1):\n",
    "                if flag:\n",
    "                    break\n",
    "                for j in range(i + 1, n):\n",
    "                    pre, aft = L[i], L[j]\n",
    "                    if pre[0] < aft[0] and pre[1] > aft[1]:\n",
    "                        to_del.append(pre)\n",
    "                        flag = True\n",
    "                        break\n",
    "                    elif pre[0] > aft[0] and pre[1] < aft[1]:\n",
    "                        to_del.append(aft)\n",
    "                        flag = True\n",
    "                        break\n",
    "            if not to_del:\n",
    "                break\n",
    "            for x, y in to_del:\n",
    "                L.remove([x, y])\n",
    "        ans = []\n",
    "        for x, y in L:\n",
    "            ans.append(s[x: y + 1])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "\n",
    "        dct = defaultdict(list)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            dct[s[i]].append(i)\n",
    "        cnt = defaultdict(list)\n",
    "        for w in dct:\n",
    "            cnt[w] = [dct[w][0], dct[w][-1]]\n",
    "\n",
    "        for i in range(26):\n",
    "            w = chr(ord(\"a\")+i)\n",
    "            if not dct[w]:\n",
    "                continue\n",
    "\n",
    "            while True:\n",
    "                x, y = cnt[w]\n",
    "                flag = 1\n",
    "                for j in range(26):\n",
    "                    ww = chr(ord(\"a\")+j)\n",
    "                    if j != i and dct[ww]:\n",
    "                        a = bisect.bisect_left(dct[ww], x)\n",
    "                        if a < len(dct[ww]) and dct[ww][a] < y and (dct[ww][0] < x or dct[ww][-1] > y):\n",
    "                            flag = 0\n",
    "                            x, y = min(x, dct[ww][0]), max(y, dct[ww][-1])\n",
    "                cnt[w] = [x, y]\n",
    "                if flag:\n",
    "                    break\n",
    "\n",
    "\n",
    "        lst = list(cnt.values())\n",
    "        lst.sort(key=lambda it: it[1])\n",
    "        m = len(lst)\n",
    "        dp = [0]*m\n",
    "        cnt = [0]*m\n",
    "        pre = [-1]*m\n",
    "        for i in range(m):\n",
    "            x, y = lst[i]\n",
    "            dp[i] = 1\n",
    "            cnt[i] = y-x+1\n",
    "            for j in range(i):\n",
    "                a, b = lst[j]\n",
    "                if b < x:\n",
    "                    if dp[j]+1>dp[i] or (dp[j]+1==dp[i] and cnt[j]+y-x+1<cnt[i]):\n",
    "                        cnt[i] = cnt[j]+y-x+1\n",
    "                        pre[i] = j\n",
    "                        dp[i] = dp[j] + 1\n",
    "        res = max(dp)\n",
    "        ind = [[i, cnt[i]] for i in range(m) if dp[i]==res]\n",
    "        ind.sort(key=lambda it: it[1])\n",
    "        res = []\n",
    "        x = ind[0][0]\n",
    "        while x != -1:\n",
    "            res.append(x)\n",
    "            x= pre[x]\n",
    "        ans = [s[lst[i][0]:lst[i][1]+1] for i in res]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        indexs = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            indexs[c].append(i)\n",
    "        # print(indexs)\n",
    "        data = [[-1, -1] for _ in range(26)]\n",
    "        for k in indexs:\n",
    "            tmp = ord(k) - ord('a')\n",
    "            st, end = indexs[k][0], indexs[k][-1]\n",
    "            l = r = st\n",
    "            while r <= end or l >= st:\n",
    "                while r <= end:\n",
    "                    \n",
    "                    st = min(st, indexs[s[r]][0])\n",
    "                    end = max(end, indexs[s[r]][-1])\n",
    "                    r += 1\n",
    "                while l >= st:\n",
    "                    idx = ord(s[l]) - ord('a')\n",
    "                    st = min(st, indexs[s[l]][0])\n",
    "                    end = max(end, indexs[s[l]][-1])\n",
    "                    l -= 1\n",
    "            data[tmp] = [st, end]\n",
    "        # 按照右端点和长度排序\n",
    "        # print(data)\n",
    "        data.sort(key=lambda x: (x[1], x[1] - x[0]))\n",
    "        ans = []\n",
    "        pre_end = -1\n",
    "        for st, end in data:\n",
    "            if st == -1 or st <= pre_end:\n",
    "                continue\n",
    "            ans.append(s[st:end+1])\n",
    "            pre_end = end\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "\n",
    "        dct = defaultdict(list)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            dct[s[i]].append(i)\n",
    "        cnt = defaultdict(list)\n",
    "        for w in dct:\n",
    "            cnt[w] = [dct[w][0], dct[w][-1]]\n",
    "\n",
    "        for i in range(26):\n",
    "            w = chr(ord(\"a\")+i)\n",
    "            if not dct[w]:\n",
    "                continue\n",
    "\n",
    "            while True:\n",
    "                x, y = cnt[w]\n",
    "                flag = 1\n",
    "                for j in range(26):\n",
    "                    ww = chr(ord(\"a\")+j)\n",
    "                    if j != i and dct[ww]:\n",
    "                        a = bisect.bisect_left(dct[ww], x)\n",
    "                        if a < len(dct[ww]) and dct[ww][a] < y and (dct[ww][0] < x or dct[ww][-1] > y):\n",
    "                            flag = 0\n",
    "                            x, y = min(x, dct[ww][0]), max(y, dct[ww][-1])\n",
    "                cnt[w] = [x, y]\n",
    "                if flag:\n",
    "                    break\n",
    "\n",
    "\n",
    "        lst = list(cnt.values())\n",
    "        lst.sort(key=lambda it: it[1])\n",
    "        m = len(lst)\n",
    "        dp = [0]*m\n",
    "        cnt = [0]*m\n",
    "        pre = [-1]*m\n",
    "        for i in range(m):\n",
    "            x, y = lst[i]\n",
    "            dp[i] = 1\n",
    "            cnt[i] = y-x+1\n",
    "            for j in range(i):\n",
    "                a, b = lst[j]\n",
    "                if b < x:\n",
    "                    if dp[j]+1>dp[i] or (dp[j]+1==dp[i] and cnt[j]+y-x+1<cnt[i]):\n",
    "                        cnt[i] = cnt[j]+y-x+1\n",
    "                        pre[i] = j\n",
    "                        dp[i] = dp[j] + 1\n",
    "        res = max(dp)\n",
    "        ind = [[i, cnt[i]] for i in range(m) if dp[i]==res]\n",
    "        ind.sort(key=lambda it: it[1])\n",
    "        res = []\n",
    "        x = ind[0][0]\n",
    "        while x != -1:\n",
    "            res.append(x)\n",
    "            x= pre[x]\n",
    "        ans = [s[lst[i][0]:lst[i][1]+1] for i in res]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumOfSubstrings(self, s: str) -> List[str]:\n",
    "        positions = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            positions[c].append(i)\n",
    "        graph = defaultdict(list)  # graph[c]表示被c所包含的子符。\n",
    "\n",
    "        for c1 in positions:\n",
    "            for c2 in positions:\n",
    "                if c1 != c2:\n",
    "                    c1_left, c1_right = positions[c1][0], positions[c1][-1]\n",
    "                    c2_position = positions[c2]\n",
    "                    if bisect_right(c2_position, c1_right) != bisect_right(c2_position, c1_left):\n",
    "                        graph[c1].append(c2)\n",
    "        subs = []\n",
    "\n",
    "        def dfs(c, visited: set) -> (int, int):\n",
    "            l, r = positions[c][0], positions[c][-1]\n",
    "            visited.add(c)\n",
    "            for nxt in graph[c]:  # 扩展\n",
    "                if nxt not in visited:\n",
    "                    nl, nr = dfs(nxt, visited)\n",
    "                    l, r = min(l, nl), max(r, nr)\n",
    "            return l, r\n",
    "\n",
    "        for c in positions:\n",
    "            visited = set()\n",
    "            c2_position, r = dfs(c, visited)  # 深度遍历搜索，包含字符c的最短子串\n",
    "            subs.append(((c2_position, r), visited))\n",
    "        subs.sort(key=lambda p: p[0][1] - p[0][0])  # 根据长度排序\n",
    "\n",
    "        left = set(positions.keys())  # 未使用的字符\n",
    "        ans = []\n",
    "\n",
    "        for (c2_position, r), visited in subs:\n",
    "            if not visited - left:  # 该子串中所有的字符都未被使用\n",
    "                ans.append(s[c2_position:r + 1])\n",
    "                left -= visited  # 移除子串中所有字符\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
